import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root != null){
            dfs(root, new ArrayDeque<>(), 0, targetSum, ans);
        }
        return ans;
    }

    void dfs(TreeNode cur, Deque<Integer> curPath, int curSum, int targetSum, List<List<Integer>> ans) {
        curSum += cur.val;
        curPath.offerLast(cur.val);
        if (isLeaf(cur)) {
            if (targetSum == curSum) {
                ans.add(new ArrayList<>(curPath));
            }
        }
        if (cur.left != null) {
            dfs(cur.left, curPath, curSum, targetSum, ans);
        }
        if (cur.right != null) {
            dfs(cur.right, curPath, curSum, targetSum, ans);
        }
        curPath.pollLast();
    }

    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
}